package com.czy.utils.tree;

import com.alibaba.fastjson.JSON;
import lombok.Data;
import lombok.NoArgsConstructor;
import org.apache.commons.lang3.StringUtils;

import javax.validation.constraints.NotNull;
import java.util.ArrayList;
import java.util.List;

/**
 * 树结构工具类
 * 树结构实体类必须实现ITree接口,并重写方法
 * @author czy
 * @date 2022-4-7 10:42
 */
public class TreeUtils {
    public static void main(String[] args) {
        List<Menu> list = new ArrayList<>();
        list.add(new Menu(1, null, "菜单1"));
        list.add(new Menu(2, null, "菜单2"));
        list.add(new Menu(3, null, "菜单3"));
        list.add(new Menu(4, 1, "菜单4"));
        list.add(new Menu(5, 1, "菜单5"));
        list.add(new Menu(6, 1, "菜单6"));
        list.add(new Menu(7, 2, "菜单7"));
        list.add(new Menu(8, 2, "菜单8"));
        list.add(new Menu(9, 3, "菜单9"));
        list.add(new Menu(10, 4, "菜单10"));
        list.add(new Menu(11, 7, "菜单11"));
        list.add(new Menu(12, 5, "菜单12"));
        list.add(new Menu(13, 10, "菜单13"));
        list.add(new Menu(14, 8, "菜单14"));
        list.add(new Menu(15, 11, "菜单15"));
        list.add(new Menu(16, 12, "菜单16"));
        list.add(new Menu(17, 13, "菜单17"));
        List<Menu> menus = TreeUtils.toTree(list,"null");
        System.out.println(JSON.toJSONString(menus));

    }

    /**
     * 集合转树结构,注意,使用此方法,则集合元素必须继承ITree接口
     * @param list 目标集合
     * @param <T> 实现ITree接口
     * @return  返回树列表
     */
    public static <T extends ITree> List<T> toTree(@NotNull List<T> list,String rootId) {
        // 1.如果目标集合为空,直接返回一个空树
        if (list == null || list.isEmpty()) {
            return null;
        }
        // 2.找出所有的根节点
        List<T> roots = getRoots(list,rootId);
        // 3.从目标集合移除所有的根节点
        list.removeAll(roots);
        // 4.为根节点添加孩子节点
        for (T tree : roots) {
            addChild(tree, list);
        }
        return roots;
    }

    /**
     * 集合转树结构,注意,使用此方法,则集合元素必须继承ITree接口
     * @param list 目标集合
     * @param <T> 实现ITree接口
     * @return  返回树列表
     */
    public static <T extends ITree> List<T> toTree(@NotNull List<T> list) {
        return toTree(list,"null");
    }

    /**
     * 找出所有的根节点
     * @param list 数据集
     * @param rootParentId 根节点父id
     * @param <T>  实现ITree接口
     * @return      返回根节点
     */
    private static <T extends ITree> List<T> getRoots(List<T> list,String rootParentId){
        List<T> roots = new ArrayList<>();
        for (T tree : list) {
            String treeParentId = tree.treeParentId();
            if (StringUtils.isNotBlank(rootParentId) && rootParentId.equals(treeParentId)){
                roots.add(tree);
            }else if (StringUtils.isBlank(treeParentId) || StringUtils.isBlank(rootParentId)) {
                roots.add(tree);
            }
        }
        return roots;
    }

    /**
     * 添加子节点
     * @param tree          某一节点
     * @param collection    非根节点数据列表
     */
    @SuppressWarnings("unchecked")
    private static void addChild(ITree tree, List<? extends ITree> collection) {
        try {
            String treeId = tree.treeId();
            List<ITree> children = (List<ITree>) tree.treeChild();
            for (ITree cc : collection) {
                String treeParentId = cc.treeParentId();
                // 如果当前节点的被依赖值和目标节点的被依赖值相等,则说明,当前节点是目标节点的子节点
                if (treeId.equals(treeParentId)) {
                    // 如果目标节点的孩子集合为null,初始化目标节点的孩子集合
                    if (children == null) {
                        children = new ArrayList<>();
                    }
                    // 将当前节点添加到目标节点的孩子节点
                    children.add(cc);
                    // 重设目标节点的孩子节点集合,这里必须重设,因为如果目标节点的孩子节点是null的话,这样是没有地址的,就会造成数据丢失,
                    // 所以必须重设,如果目标节点所在类的孩子节点初始化为一个空集合,而不是null,则可以不需要这一步,因为java一切皆指针
                    tree.insertTreeChild(children);
                    // 递归添加孩子节点
                    addChild(cc, collection);
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
            throw new RuntimeException(e);
        }
    }
}

@Data
@NoArgsConstructor
class Menu implements ITree {
    private Integer menuId;
    private Integer menuParentId;
    private String menuName;
    private List<Menu> childMenu;

    public Menu(Integer menuId, Integer menuParentId, String menuName) {
        this.menuId = menuId;
        this.menuParentId = menuParentId;
        this.menuName = menuName;
    }

    @Override
    public String treeId() {
        return String.valueOf(this.menuId);
    }

    @Override
    public String treeParentId() {
        return String.valueOf(this.menuParentId);
    }

    @Override
    public List<? extends ITree> treeChild() {
        return this.childMenu;
    }

    @Override
    @SuppressWarnings("unchecked")
    public void insertTreeChild(List<? extends ITree> children) {
        this.childMenu = (List<Menu>) children;
    }
}
